package com.peng.leetcode.graph;

import java.util.*;

/**
 * SmallestStringWithSwaps
 * <p>
 * 1202. 交换字符串中的元素
 *
 * @author: lupeng6
 * @create: 2021/1/11 17:20
 */
public class SmallestStringWithSwaps {

    public static void main(String[] args) {
        String s = "dcab";
        List<List<Integer>> pairs = new ArrayList<>();
        pairs.add(Arrays.asList(0, 3));
        pairs.add(Arrays.asList(1, 2));
        pairs.add(Arrays.asList(0, 2));
        System.out.println(new Solution().smallestStringWithSwaps(s, pairs));
        //new Solution1().smallestStringWithSwaps(s, pairs);
    }

    /**
     * 并查集
     * 将多个相互连通的操作组合成并查集,
     * 并查集, 指向父节点的反向指针 树.
     * 按照下标, 将多个能够交换的(在一个并查集内的元素) char, 按照并查集元(根)
     *
     * @author lupeng6
     * @date 2021/1/11 17:20
     */
    static class Solution {

        private int[] unionFindSet;

        private int[] level;

        public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
            unionFindSet = new int[s.length()];
            level = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                unionFindSet[i] = i;
            }
            for (List<Integer> pair : pairs) {
                union(pair.get(0), pair.get(1));
            }

            Map<Integer, PriorityQueue<Character>> map = new HashMap<>();

            for (int i = 0; i < s.length(); i++) {
                Character c = s.charAt(i);
                Integer unit = find(i);
                map.putIfAbsent(unit, new PriorityQueue<>());
                map.get(unit).offer(c);
            }

            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                int unit = find(i);
                Character c = map.get(unit).poll();
                builder.append(c);
            }
            return builder.toString();
        }


        private int find(int x) {
//            if (unionFindSet[x] != x) {
//                unionFindSet[x] = find(unionFindSet[x]);
//            }
//            return unionFindSet[x];
            int temp = x;
            while (unionFindSet[x] != x) {
                x = unionFindSet[x];
                unionFindSet[temp] = unionFindSet[x];
                temp = x;
            }
            return x;
        }

        private void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                if (level[xRoot] > level[yRoot]) {
                    // xRoot 的层级大于 yRoot 的层级, 将 xRoot 指向 yRoot
                    unionFindSet[xRoot] = yRoot;
                    level[yRoot]++;
                } else {
                    unionFindSet[yRoot] = xRoot;
                    level[xRoot]++;
                }
            }
        }
    }

    static class Solution1 {
        // 用一个列表保存并查集
        List<Integer> p;

        public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
            p = new ArrayList<>();
            int n = s.length();
            // 塞入并查集中的原始根元素
            for (int i = 0; i < n; i++) p.add(i);

            // 遍历联通节点，构建并查集
            for (List<Integer> pair : pairs) {
                int a = find(pair.get(0)), b = find(pair.get(1));

                if (a != b) p.set(a, b);
            }

            // 用一个map来保存并查集中每个集合的元素
            Map<Integer, PriorityQueue<Character>> map = new HashMap<>();

            // 将字符放到并查集中对应的集合中
            for (int i = 0; i < n; i++) {
                // 获取该下标对应的并查集中的集合
                int cur = find(i);
                if (!map.containsKey(cur)) {
                    map.put(cur, new PriorityQueue<>());
                }
                // 将该下标的字符放到对应的优先队列中
                map.get(cur).offer(s.charAt(i));
            }

            StringBuilder res = new StringBuilder();

            // 从低到高，遍历所有元素，优先poll出小的元素
            for (int i = 0; i < n; i++) {
                res.append(map.get(find(i)).poll());
            }

            return res.toString();
        }

        // 并查集中查找集合根元素的模板方法
        private int find(int x) {
            if (x != p.get(x)) {
                p.set(x, find(p.get(x)));
            }

            return p.get(x);
        }
    }

}
